class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        MOD = 10**9+7

        def dfs(s, k, memo):
            if len(s) == 0:
                return 0
            if s.startswith("0"):
                return 0
            if len(s) == 1:
                return 1 if int(s) <= k else 0
            if s in memo:
                return memo[s]
            res = 0
            for i in range(1, len(s)):
                if int(s[:i]) > k:
                    break
                res += dfs(s[i:], k, memo) % MOD

            if int(s) <= k:
                res += 1

            res %= MOD
            memo[s] = res
            return res
        return dfs(s, k, {})


if __name__ == '__main__':
    print(Solution().numberOfArrays("1234567890", 90))
